#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include "QuickSort.h"

#define UPBOUND 63  /// = 5个1

using namespace std;


int main()
{
    cout << "随机生成一列数:" << "\t";
    srand((unsigned)time(NULL));
    vector<int> A;
    for(int i = 0; i < 15; i++)
        A.push_back((int)(rand() & UPBOUND));

    for(int i = 0;i < A.size(); i++)
    cout << A[i] << " ";
    cout << endl;

    sort(A);

    cout << "使用快排后如下:" << "\t";
    for(int i = 0; i < A.size(); i++)
    cout << A[i] << " ";

    int pass = 1;
    for(int i = 0; i < A.size()-1; i++)
    if(A[i] > A[i+1]) pass = 0;

    cout << "pass = " << pass << endl;
    cout << "(这里是median-of-three法选择pivot)" << endl;

    ///以下为两种pivot选择方法对比测试
    cout << "------------------------------" << endl;
    cout << "以下为两种pivot选择方法对比测试:" << endl;

    clock_t start,end;
    srand((unsigned)time(NULL));

    std::cout << "Test 1 : 100 ramdom numbers." <<std::endl;
    vector<int> a,b;
    for(int i = 0; i < 100; i++)
    {
        int x = rand() & UPBOUND;
        a.push_back(x);
        b.push_back(x);
    }

    start = clock();
    sort(a);
    end = clock();

    double endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "median3   : " << endtime*1000 << "ms" <<endl;

    start = clock();
    randsort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "randpivot : " << endtime*1000 << "ms" <<endl;

    //
    std::cout << "Test 2 : 10000 ramdom numbers." <<std::endl;
    a.clear();
    b.clear();
    for(int i = 0; i < 10000; i++)
    {
        int x = rand() & UPBOUND;
        a.push_back(x);
        b.push_back(x);
    }

     start = clock();
    sort(a);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "median3   : " << endtime*1000 << "ms" <<endl;

    start = clock();
    randsort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "randpivot : " << endtime*1000 << "ms" <<endl;

    std::cout << "Test 3 : 1000000 ramdom numbers." <<std::endl;
    a.clear();
    b.clear();
    for(int i = 0; i < 1000000; i++)
    {
        int x = rand() & UPBOUND;
        a.push_back(x);
        b.push_back(x);
    }

     start = clock();
    sort(a);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "median3   : " << endtime*1000 << "ms" <<endl;

    start = clock();
    randsort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "randpivot : " << endtime*1000 << "ms" <<endl;

    std::cout << "Test 4 : 1000 ordered numbers." <<std::endl;
    a.clear();
    b.clear();
    for(int i = 0; i < 1000; i++)
    {
        a.push_back(i);
        b.push_back(i);
    }

     start = clock();
    sort(a);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "median3   : " << endtime*1000 << "ms" <<endl;

    start = clock();
    randsort(b);
    end = clock();

    endtime = (double)(end - start)/CLOCKS_PER_SEC;
    cout << "randpivot : " << endtime*1000 << "ms" <<endl;

    cout << "由此可见median-of-three法更有优越性" <<endl;

    return 0;
}
